package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC842 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean isFind = false;

        public List<Integer> splitIntoFibonacci(String str) {
            List<Integer> curPath = new ArrayList<>();
            splitIntoFibonacciDFS(str, 0, curPath);
            return curPath;
        }

        public void splitIntoFibonacciDFS(String str, int curVisitPos, List<Integer> curPath) {
            if (curVisitPos >= str.length()) {
                isFind = curPath.size() >= 3;
                return;
            }

            if (str.charAt(curVisitPos) == '0') {
                // 当前遍历首数字固定为0，只有第二个第三个可以变化
                if (curPath.size() <= 1 || curPath.get(curPath.size() - 2) + curPath.get(curPath.size() - 1) == 0) {
                    curPath.add(0);
                    splitIntoFibonacciDFS(str, curVisitPos + 1, curPath);
                    if (isFind) return;
                    curPath.remove(curPath.size() - 1);
                }
            } else {
                if (curPath.size() <= 1) {
                    for (int i = curVisitPos + 1; i <= str.length() && i - curVisitPos < 20 && Long.parseLong(str.substring(curVisitPos, i)) <= Integer.MAX_VALUE; i++) {
                        curPath.add(Integer.parseInt(str.substring(curVisitPos, i)));
                        splitIntoFibonacciDFS(str, i, curPath);
                        if (isFind) return;
                        curPath.remove(curPath.size() - 1);
                    }
                } else {
                    String curNeed = String.valueOf(curPath.get(curPath.size() - 2) + curPath.get(curPath.size() - 1));
                    if (curVisitPos + curNeed.length() <= str.length() && str.substring(curVisitPos, curVisitPos + curNeed.length()).equals(curNeed)) {
                        curPath.add(Integer.parseInt(curNeed));
                        splitIntoFibonacciDFS(str, curVisitPos + curNeed.length(), curPath);
                        if (isFind) return;
                        curPath.remove(curPath.size() - 1);
                    }
                }
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.splitIntoFibonacci("1101111"));
    }

    public static void main(String[] args) throws Exception {
        LC842 an = new LC842();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
